package com.sicheng.lc.周赛.分类.dp;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/10 11:20
 */
public class 统计理想数组的数目_优化 {
    //https://leetcode.cn/problems/count-the-number-of-ideal-arrays/
    static int mod = (int) (1e9 + 7);
    static int N = (int) 1e4;
    static int K = 15;
    // dp[i,j] 表示 长i以j结尾的子数组arr的种类数，arr[x-1] 是arr[x] 真因子
    static int[][] dp = new int[K + 1][N + 1];
    static int[][] c = new int[N][K];
    static ArrayList<Integer>[] p = new ArrayList[N + 1];

    // 预处理 j 的所有因子 ,dp[i,j],c[m,n]
    static {
        Arrays.setAll(p, k -> new ArrayList<>(16));
        for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j += i) {
                p[j].add(i);
            }
        }

        for (int j = 1, i = 1; j <= N; j++) {
            dp[i][j] = 1;
        }

        for (int i = 2; i <= K; i++) {
            for (int j = 1; j <= N; j++) {
                for (int k : p[j]) {
                    if (k == j)
                        break;
                    dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
                }
            }
        }

        c[0][0] = 1;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= Math.min(i, K - 1); j++) {
                if (j == 0)
                    c[i][j] = 1;
                else
                    c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
            }
        }
    }

    public int idealArrays(int n, int k) {
        // 对长为n的数组 以某个数j结尾 并且arr[x-1]  是arr[x] 的因子
        // 最终构造出的 arr数组 由 若干个k的因子组成
        //   逆向构造出原问题
        // 长为 n的数组可以看成是 不一样的因子的位置有多少种情况
        //   分步求解
        //      第一步   以j结束的因子们的情况   长i以j结束的因子的个数    dp[i,j]
        //      第二步   将i个因子插入到n个位置中去 第一个位置必须选上      c[n-1,i-1]
        //      乘法原理 统计总情况
        // 例如 n = 8 ,k =4
        //  1,2,4======>1 1 1 1 2 2 4 4 其实只要找到2,4放到哪儿 那么 间隙之间的元素都是固定的
        //  1,2,4======>1 2 2 2 2 2 2 4
        //  以上 1,2,4只是dp[3,4]的其中2种情况
        long res = 0;
        int logk = (int) (Math.log(k) / Math.log(2)) + 1;
        for (int j = 1; j <= k; j++) {
            for (int i = 1; i <= logk; i++) {
                res = (res + (long) dp[i][j] * c[n - 1][i - 1] % mod) % mod;
            }
        }
        return (int) res;
    }
    public static void main(String[] args) {
        统计理想数组的数目_优化 s = new 统计理想数组的数目_优化();

        System.out.println(s.idealArrays(1000, 1000));
        System.out.println(s.idealArrays(1000, 9000));
        System.out.println(s.idealArrays(9000, 9000));
        System.out.println(s.idealArrays(9999, 8888));
        System.out.println(s.idealArrays(5555, 6666));
        System.out.println(s.idealArrays(5555, 10000));
    }

}
